package com.mlamp动态规划问题;

import java.util.Arrays;

public class 找零钱问题 {
    public static void main(String[] args) {
        找零钱问题 instance = new 找零钱问题();
        int[] inputs = new int[]{
                1, 2, 5, 7, 10
        };
        int i = instance.minChange(inputs, 14);
        System.out.println(i);

    }


    public int minChange(int[] charges, int amount) {
        if (charges == null || charges.length < 1) return 0;
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int index = 1; index <= amount; index++) {
            dp[index] = -1;
        }
        for (int index = 1; index <= amount; index++) {
            for (int j = 0; j < charges.length; j++) {
                if (charges[j] <= index && dp[index - charges[j]] != -1) {
                    if (dp[index] == -1 || dp[index] > dp[index - charges[j]] + 1) {
                        dp[index] = dp[index - charges[j]] + 1;
                    }
                }
            }
        }
        /*for (int index = 1; index <= amount; index++) {
            for (int j = 0; j < charges.length; j++) {
                if (charges[j] < index && dp[index - charges[j]] != -1) {
                    if (dp[index] == -1 || dp[index] > dp[index - charges[j]] + 1) {
                        dp[index] = dp[index - charges[j]] + 1;
                    }
                }
            }
        }*/
        System.out.println(Arrays.toString(dp));
        return dp[amount];
    }


}
